package a12_图论;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * <p>
 * a03_所有可达路径复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/2
 */
public class a03_所有可达路径复习3 {
    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int nodeNums = scanner.nextInt();
//        int sideNums = scanner.nextInt();
//
//        int[][] grid = new int[nodeNums+1][nodeNums+1];
//        for (int i = 0; i < sideNums; i++) {
//            int x = scanner.nextInt();
//            int y = scanner.nextInt();
//            grid[x][y] = 1;
//        }

        int nodeNums = 5;
        int sideNums = 5;

        int[][] grid = new int[nodeNums+1][nodeNums+1];
        grid[1][3] = 1;
        grid[3][5] = 1;
        grid[1][2] = 1;
        grid[2][4] = 1;
        grid[4][5] = 1;

        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        path.add(1);

        traversal(result, path, grid, 1);
        if (result.isEmpty()) {
            System.out.println(-1);
        }else {
            for (List<Integer> list : result) {
                for (int i = 0; i < list.size(); i++) {
                    System.out.print(list.get(i));
                    if(i != list.size() - 1){
                        System.out.print(" ");
                    }
                }
                System.out.println();
            }
        }
    }

    private static void traversal(List<List<Integer>> result,
                           LinkedList<Integer> path,
                           int[][] grid,
                           int x){
        if(x == grid.length - 1){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int y = 1; y < grid[x].length; y++) {
            if(grid[x][y] == 0){
                continue;
            }
            path.add(y);
            traversal(result, path, grid, y);
            path.removeLast();
        }
    }
}
